import java.util.Arrays;

/**
 * 1561. 你可以获得的最大硬币数目
 * https://leetcode-cn.com/problems/maximum-number-of-coins-you-can-get/
 */
public class Solutions_1561 {
    public static void main(String[] args) {
//        int[] piles = {2, 4, 1, 2, 7, 8};  // output: 9
//        int[] piles = {2, 4, 5};  // output: 4
        int[] piles = {9, 8, 7, 6, 5, 1, 2, 3, 4};  // output: 18

        int result = maxCoins(piles);
        System.out.println(result);
    }

    /**
     * 既然没办法阻止 alice 取的最多，那就尽量剥削 bob,让 bob 取最少的
     */
    public static int maxCoins(int[] piles) {
        // 升序排列
        Arrays.sort(piles);
        int res = 0;

        // [i, len] 索引区间为取值的区间
        int len = piles.length - 1;

        // i 为 bob 取值的索引，bob 每次都拿最小的，alice 每次都拿最大的
        for (int i = 0; i <= len; i++) {
            // 自己取第二多的，即 len - 1
            res += piles[len - 1];
            len -= 2;
        }
        return res;
    }
}
